package com.company.two_tree;

/**
 * link:https://leetcode-cn.com/problems/er-cha-shu-zhong-he-wei-mou-yi-zhi-de-lu-jing-lcof/
 */

import java.util.ArrayList;
import java.util.List;

public class Solution {

    class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        TreeNode(int x) {
            val = x;
        }
    }

    private List<List<Integer>> res;

    public void track(TreeNode node, int temp, List<Integer> collection) {
        if (node == null) return;
        collection.add(node.val);
        temp -= node.val;
        if (temp == 0 && node.left == null && node.right == null) {
            res.add(new ArrayList<>(collection));
        } else {
            track(node.left, temp, collection);
            track(node.right, temp, collection);
        }
        collection.remove(collection.size() - 1);
    }

    public List<List<Integer>> pathSum(TreeNode root, int sum) {
        this.res = new ArrayList<>();
        track(root, sum, new ArrayList<>());
        return res;
    }

    public TreeNode getTree() {
        TreeNode d1 = new TreeNode(5);
        TreeNode d21 = new TreeNode(4);
        TreeNode d22 = new TreeNode(8);
        TreeNode d31 = new TreeNode(11);
        TreeNode d32 = new TreeNode(13);
        TreeNode d33 = new TreeNode(4);
        TreeNode d41 = new TreeNode(7);
        TreeNode d42 = new TreeNode(2);
        TreeNode d43 = new TreeNode(5);
        TreeNode d44 = new TreeNode(1);
        d31.left = d41;
        d31.right = d42;
        d33.left = d43;
        d33.right = d44;
        d21.left = d31;
        d22.left = d32;
        d22.right = d33;
        d1.left = d21;
        d1.right = d22;
        return d1;
    }

    public static void main(String[] args) {
        Solution solution = new Solution();

        // write your code here
        System.out.println(solution.pathSum(solution.getTree(), 22));
    }
}
